package Offer;

import java.util.Deque;
import java.util.LinkedList;

//二叉搜索树的后续遍历序列    根右左,单调栈
public class Offer33verifyPostorder {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder==null || postorder.length==0){
            return true;
        }
        int pre=Integer.MAX_VALUE;
        Deque<Integer> stack=new LinkedList<>();
        for(int i=postorder.length-1;i>=0;i--){
            if(postorder[i]>pre){
                return false;
            }
            while(!stack.isEmpty() && postorder[i]<stack.peek()){
                pre=stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}
